package com.example.algorithm.no0053.solution;

import com.example.algorithm.no0053.Solution;

/**
 * @Description 解答实现-最大子序和
 * @ClassName SolutionImpl
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class SolutionImpl implements Solution {

    // -2,1,-3,4,-1,2,-1,-5,4
    @Override
    public int maxSubArray(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int max = nums[0];    // 全局最大值
        int subMax = nums[0];  // 前一个子组合的最大值
        for (int i = 1; i < nums.length; i++) {
            if (subMax > 0) {
                // 前一个子组合最大值大于0，正增益
                subMax = subMax + nums[i];
            } else {
                // 前一个子组合最大值小于0，抛弃前面的结果
                subMax = nums[i];
            }
            // 计算全局最大值
            max = Math.max(max, subMax);
        }

        return max;
    }
}
